//
// Description: Bellman-Ford 算法模板
// Created by Loading on 2022/5/21.
//

/* 适用于在带权有向图中求解 1 号点（起点）到任意点之间的最短路径、经过不超过 k 条边的最短路径、判断负权回路等，权值可以为负 */

/*
 * 算法思想：Bellman-Ford算法是将所有边进行 n 次遍历迭代，每次迭代都更新 1 号点到其他点的最短距离。
 */

#include <bits/stdc++.h>

using namespace std;

// 点数和边数的数据范围
constexpr int N = 510, M = 10010;
// 路径权重极大值
constexpr int INF = 0x3f3f3f3f;

// dist存储 1 号点到每个点的最短距离，backup备份数组（防止更新串联）
int dist[N], backup[N];
// 点数和边数
int n, m;

// 结构体存储所有边
struct Edges {
    // 由a到b存在一条权值为w的边
    int a, b, w;
} edges[M];

/* 时间复杂度：O(nm)，n 表示点数，m 表示边数 */
// 求 1 号点到 n 号点的最短路，如果不存在则返回 INF
int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会做松弛操作，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; ++i) {
        // 防止更新距离时的串联，每次遍历要备份
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; ++j) {
            int a = edges[j].a;
            int b = edges[j].b;
            int w = edges[j].w;
            // 松弛操作
            dist[b] = min(dist[b], backup[a] + w);
        }
    }

    // 存在负权边，不能使用 dist[n] == INF 判断最短路不存在，根据数据范围选择一个较大值即可
    if (dist[n] > INF / 2) {
        return INF;
    } else {
        return dist[n];
    }
}

int main() {

}
